package 回溯.剑指;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 剑指II允许重复选择元素的组合081.java
 * @createTime 2022年10月31日 21:08:00
 */
public class 剑指II允许重复选择元素的组合081 {
	List<List<Integer>> result = new ArrayList<>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		//条件判断
		backTrace(candidates,target,0,0);
		return result;
	}

	LinkedList<Integer> list = new LinkedList<>();

	public void backTrace(int[] candidates, int target, int curIndex, int curSum) {
		//结束条件：当前值等于目标值
		if (curSum == target) {
			result.add(new ArrayList<>(list));
			return;
		}
		//如果当前值>大于目标值则停止，不在循环里面做的原因是，这是一个结束条件，不是一个选择条件。
		if (curSum > target) {
			return;
		}

		//遍历条件：遍历可以从0开始，因为是可以重复的
		for (int i = curIndex; i < candidates.length; i++) {
			//做选择，因为
			curSum += candidates[i];
			list.add(candidates[i]);
			//继续回溯，因为是可以重复的所以下一个回溯还是可以从当前的数开始
			backTrace(candidates, target, i, curSum);
			//撤销选择
			curSum -= candidates[i];
			list.removeLast();
		}
	}
}
